Searching is the most time-consuming part of many programs or applications. The substitution of a good search method for a bad one often leads to a substantial increase in speed. In fact, most common approaches often arrange the data or the data structure so that searching is eliminated entirely by ensuring that one always knows where to find the information needed. One example is sorting out the input data in ascending or descending order before finding out the maxima, minima, or any rank of the input data. Another common way to avoid searching is to apply a link list such that it is unnecessary to search for the predecessor or successor of a given item.
Search methods vary from application to application as each method has its own peculiar virtues. Some search methodologies may work well for one application but might not be the best solution for other applications. The Linear Search method is a simple way to find the maxima or minima of a given set/subset by directly comparing each element and memorizing the maximum or minimum value. This method is suitable for applications that need to repetitively find the maxima or minima of a given set. If an application needs to process every element of a given set according to its priority key (e.g., from maximum to minimum), then the sorting based approach is better than the linear search approach. For example a five channel switch might have priority keys as shown in the given set {3, 6, 10, 4, 5} with value 3 representing priority key of channel 0, and 5 representing the priority key of channel 4. The sorting based approach will rearrange the given set into {(10,ch2), (6,ch1), (5,ch4), (4,ch3), (3,ch0)} such that both the priority keys and channel number will be memorized. The search engine will then process the channel with the highest priority key and so on. This method may cause a congestion problem in logic design with large priority keys when the channel number is increasing. The problem becomes more complicated if a subset search of the master set given above needs to be performed.
SAS protocol specifies a protocol stack that provides serial physical interconnect that can be used to connect storage devices such as Hard Disk Drives (HDD) and host devices, e.g., Host Bus Adapter (HBA), together. SAS protocol specifies the transport layer protocols to transport SCSI commands, serial Advanced Technology Attachment (SATA) commands, and management commands among storage devices. The protocol is intended for use in conjunction with SCSI and SATA command sets. The SAS protocol defines the function of a SAS expander device, which is part of the service delivery subsystem and facilities communication between SAS devices. In the general sense, the SAS expanders provide the switching and routing function among the SAS devices that are attached to the given SAS expander.
Multiple SAS end devices and SAS expander devices can be connected together to form a SAS topology. There can be one or multiple physical links connecting each pair of neighbouring devices. When there is a single physical link between two devices, the associated phy on the SAS device is called a narrow port which has a dedicated SAS Address. A phy is a generic electronics term referring to a special electronic integrated circuit or functional block of a circuit that provides physical access to a digital connection cable. When there are multiple physical links connecting two devices, the associated phys on an expander are considered to be a single wide port with all the associated phys using the same dedicated SAS Address. In other words, all links of a wide port are considered to be a common logical link from a routing perspective, although multiple simultaneous connections are allowed to pass through the wide port at the same time.
The SAS topology can be as simple as connecting multiple SAS end devices through a single SAS Expander device to a Host Bus Adapter (HBA), or as complex as connecting multiple SAS end devices through multiple SAS Expander devices to multiple HBA devices in a tree structure. Each SAS end device, SAS Expander device, and HBA device has a unique dedicated SAS Address. The connection between each SAS end device to SAS Expander device or HBA device must be a narrow port, whereas the connection between SAS expander devices or between a SAS expander device and HBA device can be a narrow port (one physical link) or a single wide port (multiple physical links).
The SAS protocol adopts the point-to-point connection mechanism. The SAS end device and HBA device have to communicate to each other through the OPEN request. The SAS Expander has to perform a point-to-point connection in order to route the OPEN request from the source phy to the target phy. The communication link is considered to be set up when an OPEN request from the SAS end device is accepted by the HBA device, or an OPEN request from the HBA device is accepted by the SAS end device. At this point, information can be transferred between the HBA device and SAS end device. The OPEN requests from Multiple SAS end devices or HBA devices can reach the SAS Expander device at the same time. The SAS Expander has to perform point-to-point switching to connect the request source phy to the target phy. When there are multiple source phys requesting to be connected to the same target phy, an arbitration process is required to resolve the connection priority.
The SAS Expander device supports the least-recently-used arbitration fairness as defined in SAS protocol. The least-recently-used arbitration fairness is designed such that the longer the open request has been queuing up, the higher priority request will win the arbitration. The arbitration priority includes three parameters: the Arbitration Wait Time (AWT), the request phy SAS Address, and the Connection Rate (CONNRATE). The AWT indicates the amount of time the source phy has been waiting for the connection to the target phy. The Arbiter looks at the AWT, SAS Address, and CONNRATE in ascending order when performing the arbitration. If two source phys that are queuing for the same target phy have the same AWT, the SAS Expander device looks at the SAS Address of the source phys. The source phy that has the largest SAS Address wins the arbitration. If both source phys have the same AWT and SAS Address, the source phy that has the highest CONNRATE wins the arbitration. In the case where the AWT, SAS Address, and CONNRATE are the same for the source phys, the SAS Expander device arbitrarily picks a winner from the source phys.
The AWT, SAS Address, and CONNRATE form the arbitration priority key for the request phy. If the SAS Expander device has N physical links (where N is an integer greater than 1), the SAS Expander device may receive up to N OPEN requests at the same time. Because the SAS topology adopts a point-to-point protocol, the SAS Expander device has to arbitrate and connect the crossbar by selecting the OPEN request phy with the highest priority key one at a time. The situation becomes more complicated as the SAS topology allows narrow port and wide port connections. If a physical link with the highest priority key is requesting a connection to the wide port whose physical links are also requesting but with lower priority keys, the SAS Expander has to connect the highest priority phy to the lowest priority phy within the wide port.
There are many known sorting and searching methodologies. Unfortunately, there is no known “best” way to sort. Each method has its own advantages and disadvantages. There are many good methods, depending on what is to be sorted and for what purpose. The logic cost and search delay is of utmost importance from the SAS Expander design perspective. In the broader field of sorting and searching, some known approaches relating to the art finding maxima and minima include the straight insertion sorting method, the linear search method, the sorting based method, and the link list method.
Straight insertion sorting is the simplest method to search and sort a given set into priority order, and is quite efficient for small N. It is unbearably slow for large N unless the input is nearly in order. This searching method is also very costly for hardware design for large N as muxes are required to sort the insertion key in to priority list. The linear search is the most fundamental search method. It directly compares every element in the given set and memorizes the maximum key or minimum key. At the end of each loop, the memorized key represents the maxima or minima of the given set. The sorting based approach is when given set is sorted into a priority list with the maxima being the first element of the sorted list and the minima being the last element of the sorted list. The sorting method can use any methodology, for example the straight insertion method as mentioned above. The drawback is that if there is more than 1 master set to be sorted, e.g., to find minimum of several subsets, all of the master and subsets need to be sorted before the maxima and minima can be found. This is slow and very costly in hardware design. The link list approach, in general, combines the linear search and sorting based approaches. Each element in the master set will have an associate index to indicate the next maximum in the master set. However this method is very slow as N linear searches need to be performed in order to determine the priority index for all the N elements.
It is, therefore, desirable to provide a sorting and searching approach that overcomes at least one drawback of known approaches.